#include <unistd.h>

int has_init = 0;
void* managed_memory_start = NULL;
void* last_valid_address = NULL;

struct mem_control_block {
    int is_available;
    size_t size;
};

void malloc_init() {
    last_valid_address = sbrk(0);
    managed_memory_start = last_valid_address;
    has_init = 1;
}


void free(void* addr) {
   struct mem_control_block* mcb = addr - sizeof(struct mem_control_block);
    mcb->is_available = 1;
    return;
}

void* malloc(size_t bytes) {
    if (!has_init) {
        malloc_init();
    }

    void* current_location = NULL;
    struct mem_control_block* cur_mcb = NULL;
    void* mem_location = NULL;

    bytes += sizeof(struct mem_control_block);
    current_location = managed_memory_start;

    while (current_location != last_valid_address) {
        cur_mcb = (struct mem_control_block*) current_location;
        if (cur_mcb->is_available && cur_mcb->size >= bytes)
        {
            cur_mcb->is_available = 0;
            mem_location = current_location;
            break;
        }

        current_location = current_location + cur_mcb->size;
    }
    if (!mem_location) {
       sbrk(bytes);
       mem_location = last_valid_address;

       last_valid_address += bytes;
       cur_mcb = mem_location;
      cur_mcb->is_available = 0;
      cur_mcb->size = bytes;
    }

    mem_location = mem_location + sizeof(struct mem_location);

    return mem_location;
}
